package DataStructure.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 150. 逆波兰表达式求值 https://leetcode.cn/problems/evaluate-reverse-polish-notation
 * 题目描述：普通中缀表达式(a+b)*c-(d+e)/f 逆波兰表达式ab+c*de+f/- 求一个逆波兰表达式的值
 * todo 如何将普通中缀表达式转换为逆波兰表达式
 */
public class EvalRPN {

    public static void main(String[] args) {
        new EvalRPN().evalRPN(new String[]{"4","13","5","/","+"});
    }

    /**
     * 思路：使用一个栈，遍历表达式，若遇到数字则直接入栈，若遇到操作符，则从栈中出栈两个数进行运算并将结果放入栈中，最后栈中数字即为结果
     */
    public int evalRPN(String[] tokens) {
        Deque<Integer> numStack = new ArrayDeque<>();
        for(String s : tokens) {
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int b = numStack.removeLast();
                int a = numStack.removeLast();
                if(s.equals("+")){
                    numStack.add(a+b);
                } else if(s.equals("-")) {
                    numStack.add(a-b);
                } else if(s.equals("*")) {
                    numStack.add(a*b);
                } else if(s.equals("/")) {
                    numStack.add(a/b);
                }
            } else {
                numStack.add(Integer.valueOf(s));
            }
        }
        return numStack.remove();
    }
}
